//
//Given n pairs of parentheses, write a function to generate all combinations of
// well-formed parentheses.
// 
//
// 
//For example, given n = 3, a solution set is:
// 
// 
//[
//  "((()))",
//  "(()())",
//  "(())()",
//  "()(())",
//  "()()()"
//]
// Related Topics 字符串 回溯算法


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    fun generateParenthesis(n: Int): List<String> {
        val result = ArrayList<String>(n)
        val sb = StringBuilder()
        backTrack(result, sb, 0, 0, n)
        return result
    }

    fun backTrack(ans: MutableList<String>, sb: StringBuilder, left: Int, right: Int, n: Int) {
        if (sb.length == n * 2) {
            ans.add(sb.toString())
            return
        }
        if (left < n) {
            sb.append('(')
            backTrack(ans, sb, left + 1, right, n)
            sb.deleteCharAt(sb.length -1)
        }
        if (right < left) {
            sb.append(')')
            backTrack(ans, sb, left, right + 1, n)
            sb.deleteCharAt(sb.length -1)
        }
    }


}
//leetcode submit region end(Prohibit modification and deletion)
